﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Draco.DataStructure
{
    //除留余数法 线性探测再散列
    public class D_EasyHash<T>
    {
        private D_LinkList<int> keys = new D_LinkList<int>();

        private int addrLen = 0;
        private KeyValue?[] addr;

        private struct KeyValue
        {
            public int key;
            public T value;
        }

        public D_EasyHash(int addrLen)
        {
            this.addrLen = addrLen;
            addr = new KeyValue?[addrLen];
        }

        public D_EasyHash() : this(10) { }


        public T this[int key]
        {
            get
            {
                int i, j;
                i = Hash(key);
                if (addr[i].Value.key == key)
                {
                    return addr[i].Value.value;
                }
                else
                {
                    //线性探测再散列
                    i = (i - 1 + addrLen) % addrLen;
                    j = (i + 1) % addrLen;  
                    while (true)
                    {
                        if (j != i)
                        {
                            j = (j + 1) % addrLen;
                        }
                        else if (addr[j].Value.key == key && addr[j].Value.value!=null)
                        {
                            return addr[j].Value.value;
                        }
                        else
                        {
                            //储存地址为空的处理，或者没有添加key对于的value
                            return default(T);
                        }
                    }
                }
            }
        }

        public void Add(int key, T value)
        {
            KeyValue kv = new KeyValue();
            kv.key = key;
            kv.value = value;

            int i, j;
            i = Hash(key);
            if (!addr[i].HasValue) //存储位置为空
            {
                addr[i] = kv;
                keys.Add(key);
            }
            else
            {
                if (addr[i].Value.key == key)
                {
                    //key已经存在，添加失败
                    //throw 抛出异常
                    return;
                }
                else
                {
                    //线性探测再散列
                    i = (i - 1 + addrLen) % addrLen;
                    j = (i + 1) % addrLen;
                    while (!addr[j].HasValue)
                    {
                        if (j != i)
                        {
                            j = (j + 1) % addrLen;
                        }
                        else
                        {
                            //hash表满，添加失败
                            //throw 抛出异常
                            return;
                        }
                    }
                    addr[i] = kv;
                    keys.Add(key);
                }
            }

        }

        //除留余数法 
        public int Hash(int key)
        {
            return key % addrLen;
        }

        public bool ContainsKey(int key)
        {
            return keys.Contains(key);
        }

    }
}
